OK, well in the end I have gone for this workaround. I have known about this but it is only an option for Office XP (2002) users.
You need to install the Outlook 2002 Connector for IBM Lotus Domino
http://www.microsoft.com/downloads/details.aspx?familyid=60c4d659-3249-46cc-9cb9-db128b38e399&displaylang=en
There is no equivalent for Office 2003, nor Office 97/2000
But it really does work very well. Albeit you need to keep a very trim inbox.
Fortunately we are a reasonable small org so we are ablr to migrate users quickly, but we still have one app that has a dependancy on Excel 97, so can't take the whole office range up to XP yet.